字符串的排列

Posted on | In | | reads times

字符串的排列

题目描述

按字典序输出一个字符串的全排列
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

要深入理解递归，自身调用自身，分而治之。

  • 本篇采用的递归全排列方法
  • 递归首先应该想到，当字符串长度为1 时，其全排列就是其自身。
  • 字符串长度大于1时，将字符串分割成第一个字符和剩余字符，剩余字符全排列后，再将第一个字符与后面的字符逐个交换。
  • 值得注意的地方是，每次交换后都应将第一个字符换回原来的位置，以便下一次交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function Permutation(str)
{
    // write code here
    let res=[];
    if(str.length<=0)return res;
    var arr=str.split('');
    res=permutation(arr,0,res);
    res=[...new Set(res)];
    res.sort();
    return res;
    
    
}
function permutation(arr,index,res){
    if(arr.length===index){
        var s=''
        for(var i=0;i<arr.length;i++){
            s+=arr[i];
        }
        res.push(s);
    }
    for(var i=index;i<arr.length;i++){
        [arr[index],arr[i]]=[arr[i],arr[index]];
        permutation(arr,index+1,res);
        [arr[index],arr[i]]=[arr[i],arr[index]];
    }
    return res;
}